#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
/**
 * @brief
 * Each letter in magazine can only be used once in ransomNote.
 * 1 <= ransomNote.length, magazine.length <= 105
 * ransomNote and magazine consist of lowercase English letters.
 */
class Solution
{
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        unordered_map<char, int> ransMap, magazineMap;
        // ransomNote
        for (char r : ransomNote)
        {
            if (ransMap.find(r) == ransMap.end())
            {
                ransMap.insert({r, 1});
            }
            else
            {
                ransMap.at(r)++;
            }
        }
        // magazine
        for (char r : magazine)
        {
            if (magazineMap.find(r) == magazineMap.end())
            {
                magazineMap.insert({r, 1});
            }
            else
            {
                magazineMap.at(r)++;
            }
        }
        for (auto r : ransMap)
        {
            // has not character or count bigger
            if (magazineMap.find(r.first) == magazineMap.end() || r.second > magazineMap.at(r.first))
            {
                return 0;
            }
        }
        return 1;
    }

    bool canConstruct_2(string ransomNote, string magazine)
    {
        int hash[128];
        fill(hash, hash + 128, 0);
        for (char c : magazine)
        {
            hash[c]++;
        }
        for (char c : ransomNote)
        {
            if (hash[c] == 0)
                return false;
            hash[c]--;
        }
        return true;
    }

    bool canConstruct_3(string ransomNote, string magazine)
    {

        if (magazine.size() < ransomNote.size())
            return false;

        vector<int> histo(26, 0);

        for (auto c : magazine)
            histo[c - 'a']++;

        for (auto c : ransomNote)
        {

            histo[c - 'a']--;
            if (histo[c - 'a'] == -1)
                return false;
        }

        return true;
    }
    bool canConstruct_4(string ransomNote, string magazine)
    {
        if (magazine.size() < ransomNote.size())
            return false;
        int arr[26];
        for (int i = 0; i < 26; i++)
        {
            arr[i] = 0;
        }
        for (int i = 0; i < ransomNote.size(); i++)
        {
            arr[int(ransomNote[i]) - 97]++;
        }
        for (int i = 0; i < magazine.size(); i++)
        {
            arr[int(magazine[i]) - 97]--;
        }
        for (int i = 0; i < 26; i++)
        {
            if (arr[i] > 0)
                return false;
        }

        return true;
    }
};
int main()
{
    Solution s;
    cout << s.canConstruct("aa", "aab") << endl;
    return 0;
}
